The present invention relates to techniques for balancing packet data communications over multiple links in a bundle forming a unified interface between two nodes of a data network, particularly where some packets relate to delay-bounded communications and other packets relate to a different class of traffic.
Digital data communication is fast becoming a ubiquitous aspect of modern life. The performance of devices relying on such communications continually improves at an ever-increasing pace. As a result, there is an ever-increasing demand for communications services and an attendant increase in the bandwidth that the data communications facilities must provide.
Modern data communications utilize a variety of different forms of packet communications. Within a packet network, many of the links are point-to-point links between peer nodes. When a need for increased bandwidth on such a link arises, one option is to replace the existing link with a higher bandwidth link. However, this approach often is prohibitively expensive, particularly as an incremental upgrade. Accordingly, the solution to providing increased bandwidth often entails deploying one or more new links of similar or somewhat higher capacity in parallel to the existing link between the nodes forming the two end points. Such an upgrade forms a multilink bundle, with an aggregate bandwidth that is essentially the sum of the bandwidths or throughput rates of the parallel links in the bundle.
The multilink bundle does offer increased capacity, however, its use presents certain problems. To effectively utilize the links in the bundle as an aggregate requires that the bundle effectively appear as a single interface to each end-point node. At one logical level, all traffic intended for transport through this interface must appear as a single, unified data stream. However, within the bundle, it is necessary to segregate the traffic and distribute segments of traffic to the different links.
To maximize utilization of the parallel links within a multilink bundle, the packet communication load on the two or more parallel links must be xe2x80x9cbalanced,xe2x80x9d that is to say the volume of packet data traffic through the bundle must be optimally distributed between the various parallel links. A number of known algorithms are used to select which link to use to transport the various packets between the end-points and thereby balance the load on the links.
One type of approach manages the packet routing over the links based on link utilization. For example, when traffic on a first link reaches a certain level, the sending node shifts further packet traffic over to the next parallel link. This approach tends to load one link first, then another, and so on. Another general class of load-balancing techniques evenly distributes packets across all the links regardless of the current level of utilization of any particular link. This later approach reduces packet latency. Within this class, there are a number of specific approaches to load balancing.
One approach comprises Internet Protocol (IP) flow-based balancing. A flow is a unique conversation between two terminations on the data network. Flow-based balancing assigns each flow to one link. Once a flow is designated to use a particular link, it always goes over that link. A new flow may go over another link.
With most implementations of the flow-based balancing technique, a router or the like looks at the header of each packet and hashes all or part of the header. The IP flow-based balancing algorithms may hash different amounts of information from the header. Typically, the algorithms form a hash from the source address, the source port, the destination address and the destination port, i.e. the data from the header that uniquely defines a particular flow.
The router sends all packets with the same hash code over the same link in the bundle. The packets with the same header information produce the same hash code, and the router always assigns the packets with that hash to use the same link. Packets for communications having different headers, for example for a new session between a different source and destination, receive a different hash and may go over a different link in the point-to-point bundle. However, all packets in any one flow traverse only one link, in exactly the order received by the router. There is no need to add a sequence header or rearrange packets to compensate for different transit times over different links.
Flow-based balancing distributes flows over multiple links. However, no one flow can use all the bandwidth of all the links. If a single flow were to use more than one link, the packets may get reordered because of different packet lengths or different link latencies. There is nothing in the IP link layer to correct the order. TCP will recover packet order. However, reordering increases delays and reduces throughput. For example, it may drop a frame and request a retransmission. Hence, each flow must use a single link within the bundle. Consequently, one flow at most can access the maximum bandwidth of the largest of the channels or links within the bundle.
Many point-to-point links today use PPP, the Point-to-Point Protocol. The Multilink Protocol (RFC 1717) is a standardized extension of the PPP, which enables combination of PPP links or channels into a xe2x80x98Multilink bundlexe2x80x99 for higher rate point-to-point communications. The Multilink Protocol (MLP) uses packet fragmentation and a round-robin link assignment technique to distribute portions of data traffic over the various links within a bundle.
A typical load-balancing situation using the Multilink Protocol involves a point-to-point bundle of links between two peers, for example, between two routers. A common implementation may use multiple ISDN links between the nodes, for example basic rate or primary rate (T1) ISDN connections.
A router at one end of the bundle separates a long IP packet into two or more fragments and adds an MLP sequence header to each fragment. The load-balancing algorithm distributes the fragments taken from each packet over an appropriate number of the links, to allow parallel transmission through the bundle. In this manner, packets from a particular flow actually utilize any or all of the links in the bundle.
The communications over parallel links may encounter different delays in transmission. Fragments of one packet or succeeding packets may arrive at the receiver in a different order than when sent out over the multilink bundle. The PPP Multilink Protocol therefore uses packet sequencing to order fragments and packets. Specifically, a sequence number included in the header of each fragment of a packet allows the receiver to properly reorder the fragments and packets as they arrive over different links in the bundle.
The use of the sequence numbers, the differences in transit time through the links and the subsequent reordering all add delay and processing time. A goal is to make the bundle appear as a single point-to-point interface. In this regard it would be preferable to avoid reordering if possible.
The Multilink Protocol also provides for transport of two classes of packets, packets with sequence numbers and packets without sequence numbers. It is possible to expedite communication of a packet through the bundle by omitting the sequence number.
Using this class distinction under PPP, it becomes possible to interleave delay-sensitive traffic with packet fragments of other traffic. If the sending router receives a delay-sensitive packet, such as a voice over IP (VOIP) packet, the router can insert that packet (or fragments thereof) between the fragments of larger packets, that is to say by interleaving the delay sensitive packets between the fragments of the other packets. The delay-sensitive packet or its fragments do not receive sequence numbers. The interleaving approach works on a single point-point-point link, e.g. a single T1. However, because there is no sequence number, there is no way to handle the delay-bounded traffic over different links in a multilink bundle. The existing systems therefore have not been able to combine the fragmentation and attendant load balancing with transport of delay sensitive packets.
Per-flow load balancing techniques do not impose any additional delays due to differences in transit times through the multiple links or reorder processing caused by transport of packets of one flow over two or more links as in the Multilink fragmentation approach. However, existing per-flow balancing systems treat all traffic the same and impose the single link per flow limitation on all flows through the bundle.
Extensions to the Multilink Protocol RFC are in debate to add multiple sequence spaces to the multilink header sequence number. With these extensions, the bounded delay packets could be distributed over any link in the bundle because the receiver will guarantee that packets are received in the order sent. This proposed solution has a problem for bounded delay packets which may have fragments sent across more than one link in the bundle where the links have a large differential delay. Multilink bundles over high-speed links must be designed with 50-250 ms of differential delay because the links may traverse different geographies. Any bounded delay packets with fragments sent over these links would incur additional latency due to the differential delay.
A need therefore exists for systems and methodologies to allow transport of two or more classes of traffic through a multilink bundle, with appropriate treatments for optimal load balancing. Delay sensitive traffic should be distributed evenly over all links in the bundle, however, the system and methodologies must minimize delays and differences in delays imposed on communication of delay sensitive or delay-bounded traffic. Traffic that is not delay sensitive should be distributed evenly and in such a manner as to enable any particular communication or flow to utilize any or all of the available links, however, the combined load balancing technique should enable interleaving of the delay sensitive traffic as part of the efforts to minimize delays for such traffic.
The invention addresses the above stated needs and overcomes the stated problems by combining the multilink flow balancing technique with the per-flow balancing technique within one bundle.
One inventive aspect relates to a method of load balanced communication of packets through a bundle of data communication links between two nodes of a packet communication network. The method involves distinguishing packets for best-efforts service from packets forming delay-sensitive flows. For best-efforts service, packets are fragmented, and in preferred embodiments, headers with sequence numbers are added to the fragments. For each fragmented packet, the method entails transmitting the fragments over two or more of the links of the bundle. For a first delay-sensitive flow, the sending device calculates a first hash value from predetermined packet header data, in each packet of the flow. Similarly, the device calculates a second hash value for packets of another delay-sensitive flow. The hash values differ. Each packet for the first delay-sensitive flow is assigned to a first one of the links as a function of the first hash value, whereas each packet for the second delay-sensitive flow is assigned to a second one of the links as a function of the second hash value. The inventive method transmits packets of the first and second delay-sensitive flows over the assigned links interleaved together with the fragments transmitted on those links.
In preferred systems, such as routers or the like that implement the invention, packets for which best efforts delivery is sufficient receive Multilink Protocol treatment, that is to say with fragmentation and addition of sequence headers. Fragments of packets for any best efforts communication go over the various links within the bundle, as appropriate for load balancing on the links. For each flow of delay-bounded data, such as VOIP packets, the sending device hashes the header data and applies all packets for the flow to one of the links, assigned as a function of the hash value, for example, in standard Point-to-Point Protocol format. Different flow headers produce different hash results; therefore the device sends different delay bounded flows over the different links. Each delay-bounded flow utilizes only one of the links. Delay-bounded traffic for multiple flows utilizes all of the links in a substantially balanced manner.
An advantage of this invention is that the bounded-delay packets can be distributed over all of the links in a multilink bundle, without the risk of packet reordering or the need for sequence numbers. Packets for which xe2x80x98best-effortsxe2x80x99 service is sufficient, however, still receive the normal Multilink Protocol load-balancing treatment.
Another advantage of this invention is that it prevents differential delay between bundle links from contributing to the overall delay of bounded-delay packets. Sending all of the packets for one flow over one link, corresponding to the hash of the header information, eliminates all such differential delay problems. The relatively random selection of the link for each flow based on each new hash of a new flow header, however, balances the load of such packets produced by many such flows over all of the links within the one bundle.
Other inventive aspects relate to sending devices and receiving devices, using the inventive technique for load balanced communication of two classes of traffic through a multilink bundle. For example, one aspect relates to a device for reception of load balanced packet transmissions through a bundle of data communication links. The bundle carries fragments of packets of best efforts traffic distributed throughout the links, and the bundle carries packets for delay-sensitive flows. The packets of each delay-sensitive flow traverse a single one of the data communication links. The receiving device includes link interfaces, each of which is coupled for reception of fragments and packets over one of the data communication links. A decoder, coupled to the link interfaces, segregates the received fragments from the received packets for the delay-sensitive flows. A fragment reassembler reorders fragments received over different links as necessary and reassembles fragments into packets, for the best-efforts service. A packet router receives the reassembled packets, and this router receives delay-sensitive packets carried by a plurality of the links from the decoder without any reordering.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.